import React from 'react';

export default function index() {
  // 1\ 斐波那契函数 f(n)=f(n-1)+f(n-2)
  const fbnqFunction = (n) => {
    if (n <= 1) {
      return n;
    }
    let a = 0; // f(0)
    let b = 1; // f(1)
    let sum = 1;
    for (let i = 2; i <= n; i++) {
      sum = a + b;
      a = b; // a为f(i-1)
      b = sum; // b为f(i)
    }
    return b;
  };
  console.log(fbnqFunction(10));

  // 2\判断素数
  const isPrime = (num) => {
    // 偶数一定不是素数
    if (num % 2 == 0 || num <= 1) {
      return false;
    }
    if (num === 2) {
      return true;
    }

    for (let i = 3; i < num; i += 2) {
      if (num % i === 0) return false;
    }
    return true;
  };
  console.log(isPrime(19));
  //3\ ​将数字12345678转化成RMB形式：12,345,678
  const RMBNum = (str) => {
    const currentArr = str.split('').reverse();
    let nowArr = [];
    for (let i = 0; i < currentArr.length; i++) {
      nowArr.unshift(currentArr[i]);
      if ((i + 1) % 3 === 0 && i < currentArr.length - 1) {
        nowArr.unshift(',');
      }
    }
    return nowArr.join('');
  };
  console.log(RMBNum('112345678'));

  // 4\删除相邻相同字符串
  const getNewStr = (str) => {
    const newArr = str.split('');
    const newSet = new Set(newArr);
    const arr = [...newSet];
    return arr.join('');
  };
  console.log(getNewStr('qqqwwefg'));
  //5\贪心算法实现找零钱问题,找零数量最少
  const getMoney = (arr, target) => {
    // 排序
    const newArr = arr.sort((a, b) => b - a);
    let result = [];
    let targetCoin = target;
    for (let i of newArr) {
      while (i <= targetCoin) {
        result.push(i);
        targetCoin -= i;
      }
      if (targetCoin === 0) break;
    }
    return result;
  };
  console.log(getMoney([1, 2, 5, 25], 36));
  // 6、击鼓传花
  const quereQestion = (quere, num) => {
    while (quere.length > 1) {
      for (let i = 0; i < num; i++) {
        // 循环操作num次，每次把队首拿掉插入到队尾
        const head = quere.shift();
        quere.push(head);
      }
      quere.shift();
    }
    return `最后的赢家是${quere[0]}`;
  };
  console.log(quereQestion(['q', 's', 'f', 'a'], 3));

  // 7\来查找字符串数组中的最长公共前缀
  function longestCommonPrefix1(strs) {
    let str1 = strs[0];
    for (let i = 1; i < strs.length; i++) {
      while (strs[i].indexOf(str1) != 0) {
        // 判断当前字符串是否以str1开头，不开头则将str1从末端减少一个字母，继续比较直到相等则比较下一个str
        str1 = str1.slice(0, -1);
        if (!str1) break;
      }
    }
    return str1;
  }

  // 测试
  console.log(longestCommonPrefix1(['flower', 'flow', 'flight'])); // "fl"
  // 8\查找两个字符串最大公共部分
  const maxShareLengh = (str1, str2) => {
    let result = '';
    for (let i = 0; i < str1.length; i++) {
      for (let j = i + 1; j < str1.length; j++) {
        const str1s = str1.slice(i, j);
        if (str2.includes(str1s) && str1s.length > result.length) {
          result = str1s;
        }
      }
    }
    return result;
  };
  console.log(maxShareLengh('adcsdsfgdgdgdaa', 'fgdgdgdhh'));

  // 9、动态规划 --爬楼梯
  const pltQustion = (n) => {
    const dp = [];
    dp[0] = 0;
    dp[1] = 1;
    dp[2] = 2;
    for (let i = 3; i <= n; i++) {
      dp[i] = dp[i - 1] + dp[i - 2];
    }
    return `爬楼方法有${dp[n]}种`;
  };
  console.log(pltQustion(10));

  // 10、二叉树的最大深度
  const maxDeep = (root) => {
    let leftDeep;
    let rightDeep;
    if (!root) {
      return 0;
    } else {
      leftDeep = maxDeep(root.left);
      rightDeep = maxDeep(root.right);
      return Math.max(leftDeep, rightDeep) + 1; // 加1加上当前节点高度
    }
  };
  // 定义一颗二叉树
  class TreeNode {
    constructor(val, left = null, right = null) {
      this.val = val; // 根节点
      this.left = left; // 左子树
      this.right = right; // 右子树
    }
  }
  const tree = new TreeNode(2);
  tree.left = new TreeNode(3);
  tree.left.right = new TreeNode(4);
  tree.left.right.left = new TreeNode(5);
  console.log(maxDeep(tree), tree);

  // 11、给定两个字符串，得到使用两个字符串构成回文的最大长度大写小写需要区分
  const getHuiWen = (str1, str2) => {
    let plOfChar = {};
    let maxLength = 0;
    let hasJS = false;
    const str = str1 + str2;
    // 得到每个字母出现频率的映射
    for (const i of str) {
      plOfChar[i] = (plOfChar[i] || 0) + 1;
    }
    // 出现频率为偶数直接加到最大长度里，奇数则减1
    for (let j of Object.values(plOfChar)) {
      if (j % 2 === 0) {
        maxLength += j;
      } else {
        maxLength += j - 1;
        hasJS = true;
      }
    }
    if (hasJS) {
      return maxLength + 1;
    } else {
      return maxLength;
    }
  };
  console.log(getHuiWen('aa', 'ssffkd'));
  // 12、十进制转N进制
  const tenTransN = (num, N) => {
    if (num === 0) return num;
    if (N < 2 || N > 36) return false;
    let result = [];
    let M = num;
    // 不断用M除以N 取余数作为当前位置
    while (M > N) {
      const now = M % N;
      result.push(now);
      M = Math.floor(M / N);
    }
    result.push(M);
    for (let i = 0; i < result.length; i++) {
      if (result[i] >= 10) {
        result[i] = String.fromCharCode(65 + (result[i] - 11));
      }
    }
    return result.reverse().join('');
  };
  console.log(tenTransN(16, 16));
  // 13、得到对象最深层次
  const getObjectMaxDeep = (obj) => {
    let maxLen = 0;
    if (typeof obj != 'object') {
      return 0;
    }
    for (let i of Object.values(obj)) {
      let currentLen = 0;
      currentLen = getObjectMaxDeep(i) + 1;
      if (currentLen > maxLen) maxLen = currentLen;
    }
    return maxLen;
  };
  let obj = {
    a: 'a',
    b: {
      bb: '2b',
    },
    c: {
      cc: {
        ccc: '3c',
      },
    },
    d: {
      dd: {
        ddd: {
          dddd: '4d',
        },
      },
    },
  };
  console.log(getObjectMaxDeep(obj));
  return <div>index</div>;
}
